Reference will be made in this application to layer-2. Layer-2 is sometimes called the link layer. In addition to the link layer, there are other layers including the network layer, the physical layer and the optical layer. The traditional role of layer-2 is switching. Layer-2 services (such as frame relay, ATM, Ethernet) can be emulated over an Internet Protocol (IP) or Multi-Protocol Label Switching (MPLS) backbone by encapsulating the layer-2 packet data units (PDUs) and then transmitting them over pseudo-wires.
Virtual private local area network (LAN) service (VPLS) is an Internet-based multipoint-to-multipoint layer-2 virtual private network (L2VPN). With VPLS, multiple Ethernet LAN sites can be interconnected to each other across an MPLS backbone. To the customer, all sites that are interconnected by VPLS appear to be on the same Ethernet LAN (even though traffic travels across a service provider network).
VPLS interconnects a set of VPLS forwarders. VPLS forwarders are virtual entities inside provider edge devices (PEs). For a given VPLS instance, there is one VPLS forwarder in a given PE. Some of the forwarders are considered “spokes”, and some are considered “hubs”. In a given VPLS instance, there must be pseudo-wire binding every hub VPLS forwarder to every other hub VPLS forwarder. This means that every hub PE in the VPLS instance must have a pseudo-wire to each other hub PE in the VPLS instance. When this condition holds, we say that the VPLS instance is fully meshed. When the VPLS PEs are fully meshed, every ingress PE can send a VPLS packet to egress PE(s) directly, without the need for an intermediate PE.
It is possible that a given VPLS instance may fail to be fully meshed. This may happen for the following reasons: configuration errors, failure of the auto-discovery process, failure of the control plane to properly establish all the necessary pseudo-wires (this in turn may be due to bugs, or to resource shortages at the PEs), and failure of the data plane to carry traffic correctly on all established pseudo-wires (this can occur if there are bugs in the capsulation/de-capsulation procedures at the PEs or bugs in the forwarding procedures at intermediate nodes).
If a VPLS instance is not fully meshed, then it will not provide the LAN-like service over which its users are depending. For instance, if a link state routing algorithm is using its LAN procedures over a VPLS instance which is not fully meshed, the selected set of routes may have “black holes”.
Therefore there needs to be a mechanism in the emulated LAN to identify the falling out of full mesh status, so that appropriate steps can be taken to restore the full mesh. One known mechanism is to run Spanning-Tree Protocol (STP) over each emulated LAN pseudo-wire. This method has scaling problems because of the number of Bridge Protocol Data Units (BPDUs) that need to be sent by each VPLS forwarder.
Another known method involves each VPLS forwarder having a list of other VPLS forwarders. In addition, each VPLS forwarder has a list of VPLS forwarders with which it has established operational pseudo-wires. Identifying whether or not the full mesh status exists involves comparing the two lists. This method also has scaling problems because it requires knowing the identifiers of all the VPLS forwarders. Also the list may not be discovered at once, since the discovery can be an incremental process.